The Programmer Disk/The Programmer Disk (Microforum).iso/xpro/tutor/pro30/chap12.txt

Text File | 1991-02-04 | 29KB | 649 lines

                                                       Chapter 12
                                  POINTERS AND DYNAMIC ALLOCATION


THIS IS ADVANCED MATERIAL
_________________________________________________________________

For certain types of programs, pointers and dynamic allocation can
be a tremendous advantage, but many programs do not need such a
high degree of data structure.  For that reason, it would probably
be to your advantage to lightly skim over these topics and come
back to them later when you have a substantial base of Pascal
programming experience.  It would be good to at least skim over
this material rather than completely neglecting it, so you will
have an idea of how pointers and dynamic allocation work and that
they are available for your use when needed.

A complete understanding of this material will require deep
concentration as it is complex and not at all intuitive.
Nevertheless, if you pay close attention, you will have a good
grasp of pointers and dynamic allocation in a short time.



WHAT ARE POINTERS, AND WHAT GOOD ARE THEY?
_________________________________________________________________

Examine the program named POINT.PAS for your      ===============
first example of a program using pointers.  In       POINT.PAS
the var declaration you will see two variables    ===============
named Where and Who that have the symbol ^ in
front of their types.  This defines them, not as
variables, but as pointers to integer type variables and since they
are pointers, they store the address of data rather than the data
itself.  Note that three additional pointers are defined in line
9 which are also pointers defined with a pointer type.  The pointer
type is defined earlier in line 4.  Either method of definition can
be used and gives the same result.  Figure 12-1 is a graphical
representation of the data space prior to beginning execution of
the program.  A box represents a variable, and a box with a dot in
it represents a pointer.  In line 12 of the program, the variable
Index is assigned the value of 17 for purposes of illustration.
The pointer named Where is then assigned the address of the
variable Index which means that it does not contain the value of
17, it contains the address of the storage location where the
variable Index is stored.  In like manner, we assign the address
of Index to the pointer named Who.  It should be obvious to you
that Addr is a TURBO Pascal function that returns the address of
its argument.





                                                        Page 12-1

                     Chapter 12 - Pointers and Dynamic Allocation

HOW DO WE USE THE POINTERS?
_________________________________________________________________

It should be clear to you that we now have a single variable named
Index with two pointers pointing at it as depicted in figure 12-2.
If the pointers are useful, we should be able to do something with
them now, so we simply print out the same variable three different
ways in line 15.  When we write "Where^", we are telling the system
that we are not interested in the pointer itself, but instead we
are interested in the data to which the pointer points.  This is
referred to as dereferencing the pointer.  Careful study of the
output fields in line 15 will reveal that we first display the
value of Index, then the value to which the pointer Where points,
and finally the value to which the pointer Who points.  Since both
pointers point to the variable Index, we are essentially displaying
the value of Index three times.  You will confirm this when you
compile and run this program.

In line 17, we tell the system to assign the value of 23 to the
variable to which the pointer Where points as an illustration, and
figure 12-3 pictures the data space following this assignment.  If
you understood the discussion in the previous paragraph, you will
understand that we are actually assigning the variable named Index
the value of 23 because that is where the pointer named Where is
pointing.  In line 18, we once again display the value of the
variable Index 3 times just as we did in line 15.  It would be to
your advantage to compile and run this program to see that the
value of 17 is output three times, then the value of 23 is output
three times because in both cases, we are actually outputting the
same value three times.

In a program as simple as this, the value of pointers is not at all
clear, but a simple program is required in order to make the
technique clear.  Display the program named POINT.PAS on your
monitor again because we are not yet finished with it.



A FEW MORE POINTERS
_________________________________________________________________

In line 4, we define a new type named Int_Point which is a pointer
type to an integer variable.  We use this new type in line 9 to
define three more pointers and in line 20, we assign one of them
the address of the variable named Index.  Since the pointers are
of identical types, we can assign Pt2 the value of Pt1, as
illustrated in line 21.  This is actually the address of the
variable named Index.  Likewise, the pointer Pt3 is assigned the
value of Pt2, and we have all three pointers pointing to the
variable named Index.  TURBO Pascal will allow you to assign
pointers like this only if they are of the same type, which these
three are.  However, since the pointers named Where and Who are
declared individually, they are not of the same type according to
the rules of Pascal and if line 14 were changed in such a way that

                                                        Page 12-2

                     Chapter 12 - Pointers and Dynamic Allocation

it read "Who := Where;", a compilation error would occur.  The
variables are only assignment compatible if they are declared with
the same type name.

Finally, we assign the only variable in this program which is named
Index the value of 15 in line 23 and display the value 15 three
times as we did above.  Compile and run this program again to see
that it does indeed display the value 15 three times.  Of course,
you could write out the value 15 six times by using the other two
pointers and the variable name Index in addition to the three new
pointers.


THIS IS FOR TURBO PASCAL ONLY
_________________________________________________________________

Display the program named POINT2.PAS on your     ================
monitor for an example of another new extension     POINT2.PAS
to the Pascal programming language by Borland.   ================
This program is identical to the last example
program except in lines 13, 14 and 20, where the
symbol @ is used to denote the address of the variable Index rather
than the function Addr.  This was added to TURBO Pascal as a
convenience for you.  In ANSI standard Pascal the @ symbol is used
as a synonym for the ^ symbol but Borland chose to use it for a
completely different purpose.  Use of this symbol will result in
a program that will not compile properly with any Pascal compiler
other than TURBO Pascal.



OUR FIRST LOOK AT DYNAMIC ALLOCATION
_________________________________________________________________

If you examine the file named POINTERS.PAS, you  ================
will see a very trivial example of pointers and    POINTERS.PAS
how they are used with dynamically allocated     ================
variables.  In the var declaration, you will see
that the two variables have a ^ in front of
their respective types once again, defining two pointers.  They
will be used to point to dynamically allocated variables that have
not yet been defined.

The pointer My_Name is a pointer to a 20 character string.  The
pointer actually points to an address somewhere within the computer
memory, but we don't know where yet.  Actually, there is nothing
for it to point at because we have not defined a variable.  After
we assign it something to point to, we can use the pointer to
access the data stored at that address.

Your computer has some amount of memory installed in it. If it is
an IBM-PC or compatible, it can have up to 640K of RAM which is
addressable by various programs.  The operating system requires
about 60K of the total, and the TURBO Pascal run time system

                                                        Page 12-3

                     Chapter 12 - Pointers and Dynamic Allocation

requires about 4K to 8K depending on which version you are using,
and what functions you have called.  The TURBO Pascal program can
use up to 64K.  Adding those three numbers together results in
about 128K or 132K.  Any memory you have installed in excess of
that is available for the stack and the heap.  The stack is a
standard area defined and controlled by DOS that can grow and
shrink as needed.  Many books are available to define the stack and
its use if you are interested in more information on it.



WHAT IS THE HEAP?
_________________________________________________________________

The heap is a Pascal defined entity that utilizes otherwise unused
memory to store data.  It begins immediately following the program
and grows as necessary upward toward the stack which is growing
downward.  As long as they never meet, there is no problem.  If
they meet, a run-time error is generated.  The heap is therefore
outside of any memory limitation imposed by TURBO Pascal or any
other Pascal compiler.

Newer versions of TURBO Pascal do not limit us to 64K for the
entire program, but there are other reasons for using the heap in
addition to any memory limitation.  These should be evident as we
learn how the heap works.

If you did not understand the last few paragraphs, don't worry.
Simply remember that dynamically allocated variables are stored on
the heap and do not count in the 64K limitation placed upon you by
some compilers.


Back to our example program, POINTERS.PAS.  When we actually begin
executing the program, we still have not defined the variables we
wish to use to store data in.  The first executable statement in
line 10 generates a variable for us with no name and stores it on
the heap.  Since it has no name, we cannot do anything with it,
except for the fact that we do have a pointer My_Name that is
pointing to it.  By using the pointer, we can store up to 20
characters in it, because that is its type, and later go back and
retrieve the 20 characters.



WHAT IS DYNAMIC ALLOCATION?
_________________________________________________________________

The variable we have just described is a dynamically allocated
variable because it was not defined in a var declaration, but with
a New procedure.  The New procedure creates a variable of the type
defined by the pointer, puts the variable on the heap, and finally
assigns the address of the variable to the pointer itself.  Thus
My_Name contains the address of the variable generated.  The

                                                        Page 12-4

                     Chapter 12 - Pointers and Dynamic Allocation

variable itself is referenced by using the pointer to it followed
by a ^, just like in the last program, and is read, "the variable
to which the pointer points".

The statement in line 11 assigns a place on the heap to an integer
type variable and puts its address in My_Age.  The data space can
now be pictured as in figure 12-5.  Note that we have the data
locations defined but there is no data stored in the locations yet.

Following the New statements we have two assignment statements in
which the two variables pointed at are assigned values compatible
with their respective types, and they are both written out to the
video display in much the same manner as we did in the program
named POINT.PAS.

Following execution of lines 13 and 14, the data space is
configured as illustrated in figure 12-6.  Lines 16 and 17
illustrate that the dynamically allocated data can be used in the
same manner as any data provided the "carat" is used with the
variable name.



GETTING RID OF DYNAMICALLY ALLOCATED DATA
_________________________________________________________________

The two statements in lines 19 and 20 are illustrations of the way
the dynamically allocated variables are removed from use.  When
they are no longer needed, they are disposed of with the Dispose
procedure which frees up their space on the heap so it can be
reused.

In such a simple program, pointers cannot be appreciated, but it
is necessary for a simple illustration.  In a large, very active
program, it is possible to define many variables, dispose of some
of them, define more, and dispose of more, etc.  Each time some
variables are disposed of, their space is then made available for
additional variables defined with the New procedure.

The heap can be made up of any assortment of variables, they are
not required to be of one type.  One point must be kept in mind
however.  Anytime a variable is defined, it will have a pointer
pointing to it.  The pointer is the only means by which the
variable can be accessed.  If the pointer to the variable is lost
or changed, the data itself is lost for all practical purposes.
This will be illustrated in a later example program in this
chapter.

Compile and run this program and examine the output.  If you do not
understand how this program works, review it carefully before going
on to the next example program.




                                                        Page 12-5

                     Chapter 12 - Pointers and Dynamic Allocation

DYNAMICALLY STORING RECORDS
_________________________________________________________________

The next example program, DYNREC.PAS, is a       ================
repeat of one we studied in an earlier chapter.     DYNREC.PAS
For your own edification, review the example     ================
program BIGREC.PAS before going ahead in this
chapter.

Assuming that you are back in DYNREC.PAS, you will notice that this
program looks very similar to the earlier one, and in fact they do
exactly the same thing.  The only difference in the type
declaration is the addition of a pointer Person_Id, and in the var
declaration, the first four variables are defined as pointers here,
and were defined as record variables in the last program.

A point should be made here.  Pointers are not generally used in
very small programs.  This example program is a good bit larger
than the last few programs, and should be a clue to you as to why
such a trivial program was used to introduce pointers in this
tutorial.  A very small, concise program can illustrate a topic
much better that an large complex program, but we must go on to
more useful constructs of any new topic.  This of course, requires
more elaborate programs.


WE JUST BROKE THE GREAT RULE OF PASCAL
_________________________________________________________________

The observant student will notice that, in the type declaration we
used the identifier Person in line 18 before we defined it in line
19, which is illegal in Pascal.  Foreseeing the need to define a
pointer prior to the record, the designers of Pascal allow us to
break the rule in this one place.  The pointer could have been
defined after the record in this particular case, but it was more
convenient to put it before, and in the next example program, it
will be required to put it before the record.  We will get there
soon.

Since Friend is an array of 50 pointers, we have now defined 53
different pointers to records, but so far have defined no variables
other than Temp and Index.  We immediately use the New procedure
to dynamically allocate a record with Self pointing to it, and use
the pointer so defined to fill the dynamically allocated record.
Compare this to the program named BIGREC.PAS and you will see that
it is identical except for the addition of the New and adding the
^ to each use of the pointer to designate the data pointed to.


THIS IS A TRICK, BE CAREFUL
_________________________________________________________________

Now go down to line 48 where Mother is allocated a record and is,
by definition, pointing to the record.  It seems an easy thing to

                                                        Page 12-6

                     Chapter 12 - Pointers and Dynamic Allocation

do then to simply assign all of the values of Self to all the
values of Mother as shown in the next statement, but it doesn't
work.  The only thing the statement does is make the pointer Mother
point to the same place where Self is pointing because we did a
pointer assignment.  The data that was allocated to the pointer
Mother is now somewhere on the heap, but we don't know where, and
we cannot find it, use it, or deallocate it since we have lost the
reference to it.  This is an example of losing data on the heap.

The proper way to assign data from one record to another is given
in lines 50 and 51 where all fields of Father are defined by all
fields of Mother which is pointing at the original Self record.
Note that since Mother and Self are both pointing at the same
record, if we changed the data with either pointer, the data
appears to be changed in both because there is, in fact, only one
record where this data is stored.

In order to Write from or Read into a dynamically assigned record
it is necessary to use a temporary record since dynamically
assigned records are not allowed to be used in I/O statements.
This is illustrated in lines 57 through 63 of the program where
some data is written to the monitor.

Finally, the dynamically allocated variables are disposed of prior
to ending the program.  For a simple program such as this, it is
not necessary to dispose of them because all dynamic variables are
disposed of automatically when the program is terminated and we
return to DOS or the TURBO Pascal integrated environment.  Notice
that if the "Dispose(Mother);" statement was included in the
program, the data could not be found due to the lost pointer, and
the program would be unpredictable, possibly even resulting in a
system crash.

It would be a meaningful exercise for you to diagram the data space
for this program at a few selected points in its execution.  This
should be done in a manner similar to that done in figure 12-1 to
figure 12-5 of this chapter.


WHAT GOOD IS THIS ANYWAY?
_________________________________________________________________

Remember when you were initially studying BIGREC.PAS?  I suggested
that you see how big you could make the constant Number_Of_Friends
before you ran out of memory.  At that time we found that it could
be made slightly greater than 1000 before we got the memory
overflow message at compilation.  Try the same thing with
DYNREC.PAS to see how many records it can handle, remembering that
the records are created dynamically, so you will have to run the
program to actually run out of memory.  The final result will
depend on how much memory you have installed, and how many memory
resident programs you are using.  If you have a full memory of
640K, I would suggest you start somewhere in the neighborhood of
8000 records of Friend.

                                                        Page 12-7

                     Chapter 12 - Pointers and Dynamic Allocation


Now you should have a good idea of why dynamic allocation can be
used to greatly increase the usefulness of your programs.  There
is, however, one more important topic we must cover on dynamic
allocation.  That is the linked list.


WHAT IS A LINKED LIST?
_________________________________________________________________

Understanding and using a linked list is by far  ================
the most baffling topic you will confront in       LINKLIST.PAS
Pascal.  Many people simply throw up their hands ================
and never try to use a linked list.  I will try
to help you understand it by use of an example
and lots of explanation.  Examine the program named LINKLIST.PAS
for an example of a linked list.  I tried to keep it short so you
could see the entire operation and yet do something meaningful.

To begin with, notice that there are two types defined in lines 4
and 6, a pointer to the record and the record itself.  The record,
however, has one thing about it that is new to us, the last entry,
Next, is a pointer to a record of this type.  This record then, has
the ability to point to itself, which would be trivial and
meaningless, or to another record of the same type which will be
extremely useful in this case.  In fact, this is the way a linked
list is used.  I must point out, that the pointer to another
record, in this case called Next, does not have to be last in the
list, it can be anywhere in the list that is convenient for you.

A couple of pages ago, we discussed the fact that we had to break
the great rule of Pascal and use an identifier before it was
defined.  This is the reason the exception to the rule was allowed.
Since the pointer points to the record, and the record contains a
reference to the pointer, one has to be defined after being used,
and by rules of Pascal, the pointer can be defined first, provided
that the record is defined immediately following it.  That is a
mouthful but if you just use the syntax shown in the example, you
will not get into trouble with it.


STILL NO VARIABLES?
_________________________________________________________________

It may seem strange, but we still have no variables defined, except
for our old friend Index.  In fact, for this example, we will only
define 3 pointers.  In the last example we defined 54 pointers, and
had lots of storage room.  Before we are finished, we will have at
least a dozen pointers but they will be stored in our records, so
they too will be dynamically allocated.

Let's look at the program itself now.  In line 20, we create a
dynamically allocated record and define it by the pointer named
Place_In_List.  It is composed of the three data fields, and

                                                        Page 12-8

                     Chapter 12 - Pointers and Dynamic Allocation

another pointer.  We define Start_Of_List to point to the first
record created, and we will leave it unchanged throughout the
program.  The pointer Start_Of_List will always point to the first
record in the linked list which we are building up.  The data space
is as depicted in figure 12-7.


WHAT IS "nil" AND WHAT IS IT USED FOR?
_________________________________________________________________

We define the three variables in the record to be any name we
desire for illustrative purposes, and set the pointer in the record
to nil.  The word nil is another reserved word that doesn't give
the pointer an address but defines it as empty.  A pointer that is
currently nil cannot be used to manipulate data because it has no
value, but it can be tested in a logical statement to see if it is
nil.  It is therefore a dummy assignment.  With all of that, the
first record is completely defined.


DEFINING THE SECOND RECORD
_________________________________________________________________

When you were young you may have played a searching game in which
you were given a clue telling you where to find the next clue.  The
next clue had a clue to the location of the third clue.  You kept
going from clue to clue until you found the prize.  You simply
exercised a linked list.  We will now build up the same kind of a
list in which each record will tell us where the next record can
be found.

In lines 27 through 33 we will define the second record.  Our goal
will be to store a pointer to the second record in the pointer
field of the first record.  In order to keep track of the last
record, the one in which we need to update the pointer, we will
keep a pointer to it in Temp_Place.  Now we can dynamically
allocate another new record and use Place_In_List to point to it.
Since Temp_Place is now pointing at the first record, we can use
it to store the value of the pointer which points to the new record
which we do in line 29.  The 3 data fields of the new record are
assigned nonsense data for our illustration, and the pointer field
of the new record is assigned nil.  We have reached the point when
the data space is as depicted in figure 12-8.

Let's review our progress to this point.  We now have the first
record with a person's name and a pointer to the second record, and
a second record containing a different person's name and a pointer
assigned nil.  We also have three pointers, one pointing to the
first record, one pointing to the last record, and one we used just
to get here since it is only a temporary pointer.  If you
understand what is happening so far, let's go on to add some
additional records to the list.  If you are confused, go back over
this material again.


                                                        Page 12-9

                     Chapter 12 - Pointers and Dynamic Allocation


TEN MORE RECORDS
_________________________________________________________________

The next section of code is contained within a for loop so the
statements are simply repeated ten times.  If you observe
carefully, you will notice that the statements are identical to the
second group of statements in the program (except of course for the
name assigned).  They operate in exactly the same manner, and we
end up with ten more names added to the list.  You will now see why
the temporary pointer was necessary, but pointers use little memory
and are therefore relatively cheap, so feel free to use them at
will.  A pointer generally uses only 4 bytes of memory.


FINALLY, A COMPLETE LINKED LIST
_________________________________________________________________

We now have generated a linked list of twelve entries.  We have a
pointer pointing at the first entry, and another pointer pointing
at the last.  The only data stored within the program itself are
three pointers, and one integer, all of the data is on the heap.
This is one advantage to a linked list, it uses very little local
memory, but it is costly in terms of programming.  (Keep in mind
that all of the data must be stored somewhere in memory, and in the
case of the linked list, it is stored on the heap.)  You should
never use a linked list simply to save memory, but only because a
certain program lends itself well to it.  Some sorting routines are
extremely fast because of using a linked list, and it could be
advantageous to use in a database.



HOW DO WE GET TO THE DATA NOW?
_________________________________________________________________

Since the data is in a list, how can we get a copy of the fourth
entry for example?  The only way is to start at the beginning of
the list and successively examine pointers until you reach the
desired one.  Suppose you are at the fourth and then wish to
examine the third.  You cannot back up, because you didn't define
the list that way, you can only start at the beginning and count
to the third.  You could have defined the record with two pointers,
one pointing forward, and one pointing backward.  This would be a
doubly-linked list and you could then go directly from entry four
to entry three.

Now that the list is defined, we will read the data from the list
and display it on the video monitor.  We begin by defining the
pointer, Place_In_List, as the start of the list.  Now you see why
it was important to keep a copy of where the list started.  In the
same manner as filling the list, we go from record to record until
we find the record with the value nil stored in its pointer.


                                                       Page 12-10

                     Chapter 12 - Pointers and Dynamic Allocation

There are entire books on how to use linked lists, and most Pascal
programmers will seldom, if ever, use them.  For this reason,
additional detail is considered unnecessary, but to be a fully
informed Pascal programmer, some insight is necessary.



PROGRAMMING EXERCISE
_________________________________________________________________

1.   Write a program to store a few names dynamically, then display
     the stored names on the monitor.  As your first exercise in
     dynamic allocation, keep it very simple.










































                                                       Page 12-11